//封装哈希表类
function HashTable() {
  // 属性
  this.storage = [];
  this.count = 0; //计算已经存储的元素个数
  this.limit = 7; //哈希表总长度

  // 方法
  // 0.哈希函数
  HashTable.prototype.hashFunc = function (str, size) {
    //定义一个hashCode变量
    let hashCode = 0;
    //2，霍纳算法，来计算hashCode的值
    for (let i = 0; i < str.length; i++) {
      //cats-> Uniccde编码 , 拿到每一个字符的编码
      hashCode = 37 * hashCode + str.charCodeAt(i);
    }
    // 3.取余操作
    let index = hashCode % size;
    return index;
  };

  // 2.插入与修改操作
  HashTable.prototype.put = function (key, value) {
    //1，根据key获取对应的index
    let index = this.hashFunc(key, this.limit);

    //2，根据index取出对应的bucket
    let bucket = this.storage[index];

    //3，判断该bucket是否为null
    if (bucket == null) {
      bucket = [];
      this.storage[index] = bucket;
    }

    //4，判断是否是修改数据
    for (let i = 0; i < bucket.length; i++) {
      let tuple = bucket[i]; //tuple 是一个数组
      if (tuple[0] == key) {
        tuple[1] = value;
        return;
      }
    }

    //5.添加数据操作
    bucket.push([key, value]);
    this.count++;

    // 6.判断是否需要扩容操作
    if (this.count > this.limit * 0.75) {
      let newPrime = this.getPrime(this.limit * 2); //获取质数
      this.resize(newPrime); //扩容操作
    }
  };

  // 3.根据key获取操作
  HashTable.prototype.get = function (key) {
    //1，根据key获取对应的index
    let index = this.hashFunc(key, this.limit);
    // 2.根据我们的index获取对应的bucket
    let bucket = this.storage[index];
    // 3.通是否为null
    if (bucket == null) {
      return null;
    }
    //4.有bucket，那么就进行线性查找
    for (let i = 0; i < bucket.length; i++) {
      let tuple = bucket[i];
      if (tuple[0] == key) {
        return tuple[1];
      }
    }
    //5，依然没有找到，那么返回null
    return null;
  };

  // 4.删除操作
  HashTable.prototype.remove = function (key) {
    //1，根据key获取对应的index
    let index = this.hashFunc(key, this.limit);
    // 2.根据我们的index获取对应的bucket
    let bucket = this.storage[index];
    // 3.通是否为null
    if (bucket == null) {
      return false;
    }
    //4.有bucket，那么就进行线性查找
    for (let i = 0; i < bucket.length; i++) {
      let tuple = bucket[i];
      if (tuple[0] == key) {
        bucket.splice(i, 1);
        this.count--;

        //缩小容量
        if (this.limit > 7 && this.count < this.limit * 0.25) {
          let newPrime = this.getPrime(this.limit / 2); //获取质数
          this.resize(Math.floor(newPrime));
        }

        return tuple[1];
      }
    }

    //5，依然没有找到，那么返回null
    return false;
  };

  //其他方法
  //1.判断哈希表是否为null
  HashTable.prototype.isEmpty = function () {
    return this.count == 0;
  };

  //2.获取哈希表中元素的个数
  HashTable.prototype.size = function () {
    return this.count;
  };

  //哈希表扩容
  HashTable.prototype.resize = function (newLimit) {
    //1，保存旧的数组内容
    let oldStorage = this.storage;

    // 2.重置所有的属性
    this.storage = [];
    this.count = 0;
    this.limit = newLimit;

    //3.遍历oldStorage中所有的bucket
    for (let i = 0; i < oldStorage.length; i++) {
      //3.1，取出对应的bucket
      let bucket = oldStorage[i];
      // 3.2 判断bucket是否为null
      if (bucket == null) {
        continue;
      }
      //3.3 bucket中有数据，那么取出数据，重新插入
      for (let j = 0; j < bucket.length; j++) {
        let tuple = bucket[j];
        this.put(tuple[0], tuple[1]);
      }
    }
  };

  //拓展
  //1.高效判断是不是质数的方法
  HashTable.prototype.isPrime = function (num) {
    // 1.获取平方根
    let temp = parseInt(Math.sqrt(num));

    // 循环判断
    for (let i = 0; i < temp; i++) {
      if (num % i == 0) {
        return false;
      }
    }
    return true;
  };

  //2.获取质数的方法
  HashTable.prototype.getPrime = function (num) {
    while (!this.isPrime(num)) {
      //判断不是一个质数
      num++;
    }
    return num;
  };
}

// 测试哈希表
//1，创建哈希表
let ht = new HashTable();

//2，插入数据
ht.put("AA", "我是valueA");
ht.put("BB", "我是valueB");
ht.put("CC", "我是valueC");
ht.put("DD", "我是valueD");
console.log(ht);

console.log(ht.get("DD"));
console.log("我删除了", ht.remove("CC"));
console.log(ht.get("CC"));

console.log(ht);
